package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 杨辉三角一
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/13 11:39
 */
public class E118 {

    /**
     * <h3>方法一：迭代，正常放</h3>
     *
     * @param numRows 行数
     * @return 杨辉三角
     */
    public List<List<Integer>> generate1(int numRows) {
        List<List<Integer>> result = new ArrayList<>(numRows);
        for (int i = 1; i <= numRows; i++) {
            ArrayList<Integer> list = new ArrayList<>(i);
            if (i == 1) {
                list.add(1);
                result.add(list);
                continue;
            }
            if (i == 2) {
                list.add(1);
                list.add(1);
                result.add(list);
                continue;
            }
            List<Integer> last = result.get(i - 2);
            list.add(1);
            for (int j = 0; j < i - 2; j++) {
                list.add(last.get(j) + last.get(j + 1));
            }
            list.add(1);
            result.add(list);
        }
        return result;
    }

    // 1
    // 1 1
    // 1 2 1
    // 1 3 3 1
    // 1 4 6 4 1

    /**
     * <h3>方法二：迭代，放成一个三角形，更直观，推荐</h3>
     * @param numRows 行数
     * @return 杨辉三角
     */
    public List<List<Integer>> generate2(int numRows) {
        List<List<Integer>> result = new ArrayList<>(numRows);
        for (int i = 0; i < numRows; i++) {
            List<Integer> list = new ArrayList<>(i + 1);
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    list.add(1);
                } else if (i != j) {
                    list.add(result.get(i - 1).get(j - 1) + result.get(i - 1).get(j));
                } else {
                    list.add(1);
                }
            }
            result.add(list);
        }
        return result;
    }

    /**
     * <h3>递归实现，不规范</h3>
     * @param numRows 行数
     * @return 杨辉三角
     */
    public List<List<Integer>> generate3(int numRows) {
        if (numRows == 1){
            List<List<Integer>> result = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
            list.add(1);
            result.add(list);
            return result;
        }
        if (numRows == 2){
            List<List<Integer>> result = generate3(1);
            List<Integer> list = new ArrayList<>();
            list.add(1);
            list.add(1);
            result.add(list);
            return result;
        }
        List<Integer> currentRow = new ArrayList<>();
        List<List<Integer>> last = generate3(numRows - 1);
        List<Integer> lastRow = last.get(numRows - 2);
        currentRow.add(1);
            for (int i = 1; i < numRows - 1 ; i++) {
            currentRow.add(lastRow.get(i -1) + lastRow.get(i));
        }
        currentRow.add(1);
        last.add(currentRow);
        return last;
    }

    /**
     * <h3>递归实现，更优雅，推荐</h3>
     * @param numRows 行数
     * @return 杨辉三角
     */
    public List<List<Integer>> generate4(int numRows){
        List<List<Integer>> result = new ArrayList<>();
        generate4(result, numRows);
        return result;
    }

    /**
     * 递归实现
     * @param result 结果
     * @param numRows 行
     */
    private void generate4(List<List<Integer>> result, int numRows){
        if (numRows == 0){
            return;
        }
        generate4(result, numRows - 1);
        List<Integer> currentRow = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            if (i == 0 || i == numRows - 1){
                currentRow.add(1);
            }else {
                currentRow.add(result.get(numRows - 2).get(i - 1) + result.get(numRows - 2).get(i));
            }
        }
        result.add(currentRow);
    }

    /**
     * <h3>方法五：组合数，推荐</h3>
     * @param numRows 行数
     * @return 返回杨辉三角
     */
    public List<List<Integer>> generate5(int numRows){
        List<List<Integer>> result = new ArrayList<>(numRows);
        for (int i = 0; i < numRows; i++) {
            ArrayList<Integer> currentRow = new ArrayList<>(i + 1);
            for (int j = 0; j <= i; j++) {
                currentRow.add((int) combination(i, j));
            }
            result.add(currentRow);
        }
        return result;
    }

    /**
     * 计算组合数C(n, m)，优化后的，没有用阶乘
     * @param n 总数
     * @param m 选择的个数
     * @return 组合数
     */
    private long combination(int n, int m){
        if (m > n) {
            return 0;
        }
        if (m == 0 || m == n) {
            return 1;
        }
        m = Math.min(m, n - m); // C(n, m) = C(n, n - m)，选最小的计算快
        long result = 1;
        for (int i = 0; i < m; i++) {
            // C(n, m) == n / m * C(n - 1, m - 1)
            //         == n / m * (n - 1) / (m - 1) * C(n - 2, m - 2)
            //         == n / m * (n - 1) / (m - 1) * (n - 2) / (m - 2) * ... (n - m + 1) / (m - m + 1) * C(n - m, 0)
            //         == n / m * (n - 1) / (m - 1) * (n - 2) / (m - 2) * ... (n - m + 1) / (1) * 1
            //         == n * (n - 1) * ... (n - m + 1) / m! (分母的数字换位置)
            //         == n / 1 * (n - 1) / 2 * ... (n - m + 1) / m（这一部分就是下面的原理）
            result = result * (n - i) / (i + 1);
        }
        return result;
    }

    /**
     * <h3>方法六：采用C(n, m - 1)和C(n, m)之间的关系进行求解，推荐</h3>
     * @param numRows 行数
     * @return 返回杨辉三角
     */
    public List<List<Integer>> generate6(int numRows){
        List<List<Integer>> result = new ArrayList<>(numRows);
        for (int i = 0; i < numRows; i++) {
            ArrayList<Integer> currentRow = new ArrayList<>(i + 1);
            currentRow.add(1);
            for (int j = 1; j <= i; j++) {
                currentRow.add((int) ((long) currentRow.get(j - 1) * (i - j + 1) / j));
            }
            result.add(currentRow);
        }
        return result;
    }

    /**
     * <h3>方法七：用动态规划求解，用二维数组</h3>
     * @param numRows 行数
     * @return 返回杨辉三角
     */
    public List<List<Integer>> generate7(int numRows){
        List<List<Integer>> result = new ArrayList<>(numRows);
        int[][] dp = new int[numRows][numRows];
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0 || i == j){
                    dp[i][j] = 1;
                }else {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }
            }
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                list.add(dp[i][j]);
            }
            result.add(list);
        }
        return result;
    }

    /**
     * <h3>方法八：用动态规划求解，优化为一维数组，推荐</h3>
     * @param numRows 行数
     * @return 返回杨辉三角
     */
    public List<List<Integer>> generate8(int numRows){
        List<List<Integer>> result = new ArrayList<>(numRows);
        int[] dp = new int[numRows];
        for (int i = 0; i < numRows; i++) {
            for (int j = i; j >= 0; j--) { // 这里要倒序，因为要保证dp[j - 1] + dp[j]的dp[j - 1]是上一轮的，如果是正序的话，dp[j]是上一轮的，dp[j - 1]是当前轮的，会出错。
                if (j == 0 || i == j){
                    dp[j] = 1;
                }else {
                    dp[j] = dp[j - 1] + dp[j];
                }
            }
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                list.add(dp[j]);
            }
            result.add(list);
        }
        return result;
    }
}
